home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / pcb-1.000 / pcb-1 / pcb-1.3 / find.c < prev    next >
C/C++ Source or Header  |  1995-03-01  |  40KB  |  1,388 lines
  1. /*
  2.  *                            COPYRIGHT
  3.  *
  4.  *  PCB, interactive printed circuit board design
  5.  *  Copyright (C) 1994,1995 Thomas Nau
  6.  *
  7.  *  This program is free software; you can redistribute it and/or modify
  8.  *  it under the terms of the GNU General Public License as published by
  9.  *  the Free Software Foundation; either version 2 of the License, or
  10.  *  (at your option) any later version.
  11.  *
  12.  *  This program is distributed in the hope that it will be useful,
  13.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.  *  GNU General Public License for more details.
  16.  *
  17.  *  You should have received a copy of the GNU General Public License
  18.  *  along with this program; if not, write to the Free Software
  19.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20.  *
  21.  *  Contact addresses for paper mail and Email:
  22.  *  Thomas Nau, Schlehenweg 15, 88471 Baustetten, Germany
  23.  *  Thomas.Nau@rz.uni-ulm.de
  24.  *
  25.  */
  26.  
  27. static    char    *rcsid = "$Header: /sda4/users/nau/src/pcb/RCS/find.c,v 2.1 1994/09/28 14:26:11 nau Exp nau $";
  28.  
  29. /*
  30.  * short description:
  31.  * - all pin and via pointers are copied to a single array to have linear
  32.  *   access to them. All pointers refer to this list.
  33.  * - two fields, with pointers to line data, are build for each layer
  34.  *   sorted by:
  35.  *     -  the lower x line coordinates in decending order and
  36.  *     -  the higher x line coordinates in asscending order.
  37.  *   They are used to have fewer accesses when looking for line connections.
  38.  * - lists for pins and vias, for lines and for polygons are created.
  39.  *   Every object that has to be checked is added to its list.
  40.  * - there's no 'speed-up' mechanism for polygons because they are not used
  41.  *   as often as lines and are much easier to handle
  42.  * - the maximum distance between line and pin ... would depend on the angle
  43.  *   between them. To speed up computation the limit is set to one third
  44.  *   of the thickness of the objects which is close to 
  45.  *   thickness/2/sqrt(2). The result is that connections between objects
  46.  *   with a distance close to that limit are not recognized.
  47.  *
  48.  * PV:  means pin or via (objects that connect layers)
  49.  * LO:  all non PV objects (layer related objects like lines)
  50.  *
  51.  * 1. first, the PV at the given coordinates is looked up
  52.  * 2. all LO connections to that PV are looked up next
  53.  * 3. lookup of all LOs connected to LOs from (2).
  54.  *    This step is repeated until no more new connections are found.
  55.  * 4. lookup all PVs connected to the LOs from (2) and (3)
  56.  * 5. start again with (1) for all new PVs from (4)
  57.  *
  58.  * Intersection of line <--> circle:
  59.  * - calculate the signed distance from the line to the center,
  60.  *   return false if abs(distance) > R
  61.  * - get the distance from the line <--> distancevector intersection to
  62.  *   (X1,Y1) in range [0,1], return true if 0 <= distance <= 1
  63.  * - depending on (r > 1.0 or r < 0.0) check the distance of X2,Y2 or X1,Y1
  64.  *   to X,Y
  65.  * - There is a maximum difference between the inner circle
  66.  *   of a PV and the outer one of 8.2% of its radius.
  67.  *   This difference is ignored which means that lines that end
  68.  *   right at the corner of a PV are not recognized.
  69.  *
  70.  * Intersection of line <--> line:
  71.  * - see the description of 'LineLineIntersect()'
  72.  */
  73.  
  74. /* routines to find connections between pins, vias, lines...
  75.  */
  76.  
  77. #include <stdlib.h>
  78. #include <string.h>
  79. #include <math.h>
  80. #include <sys/times.h>
  81.  
  82. #include "global.h"
  83.  
  84. #include "data.h"
  85. #include "dialog.h"
  86. #include "draw.h"
  87. #include "find.h"
  88. #include "mymem.h"
  89. #include "misc.h"
  90. #include "search.h"
  91. #include "set.h"
  92.  
  93. /* ----------------------------------------------------------------------
  94.  * some math constants
  95.  */
  96. #ifndef M_SQRT1_2    /* 1/sqrt(2) */
  97. #define    M_SQRT1_2    0.70710678118654752440
  98. #endif
  99.  
  100. /* ---------------------------------------------------------------------------
  101.  * some local macros
  102.  */
  103. #define    SEPERATE(FP)                            \
  104.     {                                            \
  105.         int    i;                                    \
  106.         for (i = Settings.CharPerLine; i; i--)    \
  107.             fputc('=', (FP));                    \
  108.         fputc('\n', (FP));                        \
  109.     }
  110.  
  111. #define    LINELIST_ENTRY(L,I)    \
  112.     (((LineTypePtr *)LineList[(L)].Data)[(I)])
  113.  
  114. #define    POLYGONLIST_ENTRY(L,I)    \
  115.     (((PolygonTypePtr *)PolygonList[(L)].Data)[(I)])
  116.  
  117. #define    PVLIST_ENTRY(I)    \
  118.     (((PVDataTypePtr *)PVList.Data)[(I)])
  119.  
  120. #define    IS_PV_ON_LINE(PV,Line)    \
  121.     (IsPointOnLine((PV)->X,(PV)->Y,(PV)->Thickness/2+1,(Line)))
  122.  
  123. #define    ADD_PV_TO_LIST(Ptr)                    \
  124. {                                            \
  125.     SET_FLAG(FOUNDFLAG, (Ptr)->Data);        \
  126.     PVLIST_ENTRY(PVList.Number) = (Ptr);    \
  127.     PVList.Number++;                        \
  128. }
  129.  
  130. #define    ADD_LINE_TO_LIST(L,Ptr)                            \
  131. {                                                        \
  132.     SET_FLAG(FOUNDFLAG, (Ptr));                            \
  133.     LINELIST_ENTRY((L),LineList[(L)].Number) = (Ptr);    \
  134.     LineList[(L)].Number++;                                \
  135. }
  136.  
  137. #define    ADD_POLYGON_TO_LIST(L,Ptr)                            \
  138. {                                                            \
  139.     SET_FLAG(FOUNDFLAG, (Ptr));                                \
  140.     POLYGONLIST_ENTRY((L), PolygonList[(L)].Number) = (Ptr);\
  141.     PolygonList[(L)].Number++;                                \
  142. }
  143.  
  144. /* ---------------------------------------------------------------------------
  145.  * some local types
  146.  */
  147. typedef struct
  148. {
  149.     void        **Data;            /* pointer to index data */
  150.     Cardinal    Position,        /* currently used position */
  151.                 DrawPosition,
  152.                 Number;            /* number of objects in list */
  153. } ListType, *ListTypePtr;
  154.  
  155. typedef struct                    /* holds a copy of all pins and vias */
  156. {                                /* plus a pointer to the according element */
  157.     PinTypePtr        Data;
  158.     ElementTypePtr    Element;
  159. } PVDataType, *PVDataTypePtr;
  160.  
  161. /* ---------------------------------------------------------------------------
  162.  * some local identifiers
  163.  */
  164. static    Widget            Popup;                        /* abort dialog and flag */
  165. static    Boolean            Abort;
  166. static    LineTypePtr        *LineSortedByLowX[MAX_LAYER],    /* sorted array of */
  167.                         *LineSortedByHighX[MAX_LAYER];    /* line pointers */
  168. static    PVDataTypePtr    PVSortedByX;                /* same for PV */
  169. static    Cardinal        TotalPV;                    /* total number of PV */
  170. static    ListType        LineList[MAX_LAYER],        /* list of objects to */
  171.                         PolygonList[MAX_LAYER],
  172.                         PVList;
  173.  
  174. /* ---------------------------------------------------------------------------
  175.  * some local prototypes
  176.  */
  177. static    void        CB_Abort(Widget, XtPointer, XtPointer);
  178. static    void        CreateAbortDialog(void);
  179. static    Boolean        CheckAbort(void);
  180. static    int            CompareLineByLowX(const void *, const void *);
  181. static    int            CompareLineByHighX(const void *, const void *);
  182. static    int            ComparePVByX(const void *, const void *);
  183. static    Cardinal    GetLineByLowX(Position, Cardinal);
  184. static    Cardinal    GetLineByHighX(Position, Cardinal);
  185. static    Cardinal    GetPVByX(Position);
  186. static    void        FreeConnectionLookupMemory(void);
  187. static    void        InitConnectionLookup(void);
  188. static    LineTypePtr    *GetIndexOfLines(Position, Position, Cardinal, Cardinal *);
  189. static    PVDataType    *LookupPVByCoordinates(Position, Position);
  190. static    void        LookupLOConnectionsToPVList(void);
  191. static    void        LookupLOConnectionsToLOList(void);
  192. static    void        LookupPVConnectionsToLOList(void);
  193. static    void        LookupLOConnectionsToLine(LineTypePtr, Cardinal);
  194. static    void        LookupLOConnectionsToPolygon(PolygonTypePtr, Cardinal);
  195. static    Boolean        IsLineInPolygon(LineTypePtr, PolygonTypePtr);
  196. static    Boolean        IsPolygonInPolygon(PolygonTypePtr, PolygonTypePtr);
  197. static    Boolean        PrintElementConnections(ElementTypePtr, FILE *);
  198. static    Boolean        LineLineIntersect(LineTypePtr, LineTypePtr);
  199. static    Boolean        ListsEmpty(void);
  200. static    void        DoIt(void);
  201. static    void        PrintPinConnections(FILE *);
  202. static    Boolean        PrintAndSelectUnusedPinsOfElement(ElementTypePtr, FILE *);
  203. static    void        DrawNewConnections(void);
  204. static    void        ResetConnections(void);
  205.  
  206. /* ---------------------------------------------------------------------------
  207.  * callback for 'AbortDialog' dialog
  208.  */
  209. static void CB_Abort(Widget W, XtPointer ClientData, XtPointer CallData)
  210. {
  211.     Abort = True;
  212. }
  213.  
  214. /* ---------------------------------------------------------------------------
  215.  * creates an 'Abort' dialog
  216.  */
  217. static void CreateAbortDialog()
  218. {
  219.     static    DialogButtonType    buttons[] = {
  220.         { "defaultButton", " Abort ", CB_Abort, (XtPointer) NULL, NULL }};
  221.  
  222.         /* create dialog box */
  223.     Popup = CreateDialogBox("press button to abort 'scanning of connections'",
  224.         buttons, ENTRIES(buttons));
  225.     Abort = False;
  226.     StartDialog(Popup);
  227. }
  228.  
  229. /* ---------------------------------------------------------------------------
  230.  * dispatches all events and returns the status of
  231.  * 'Abort'
  232.  */
  233. static Boolean CheckAbort(void)
  234. {
  235.     XEvent    event;
  236.  
  237.     while (XtAppPending(Context))
  238.     {
  239.         XtAppNextEvent(Context, &event);
  240.         XtDispatchEvent(&event);
  241.     }
  242.     return(Abort);
  243. }
  244.  
  245. /* ---------------------------------------------------------------------------
  246.  * quicksort compare function for line coordinate X1
  247.  * line field is sorted in decending order of X1
  248.  */
  249. static int CompareLineByLowX(const void * Index1, const void * Index2)
  250. {
  251.     LineTypePtr    ptr1 = *((LineTypePtr *) Index1),
  252.                 ptr2 = *((LineTypePtr *) Index2);
  253.  
  254.     return((int) (MIN(ptr2->X1, ptr2->X2) -MIN(ptr1->X1, ptr1->X2)));
  255. }
  256.  
  257. /* ---------------------------------------------------------------------------
  258.  * quicksort compare function for line coordinate X2
  259.  * line field is sorted in ascending order of X2
  260.  */
  261. static int CompareLineByHighX(const void * Index1, const void * Index2)
  262. {
  263.     LineTypePtr    ptr1 = *((LineTypePtr *) Index1),
  264.                 ptr2 = *((LineTypePtr *) Index2);
  265.  
  266.     return((int) (MAX(ptr1->X1, ptr1->X2) -MAX(ptr2->X1, ptr2->X2)));
  267. }
  268.  
  269. /* ---------------------------------------------------------------------------
  270.  * quicksort compare function for pin (via) coordinate X
  271.  * for sorting the PV field in ascending order of X
  272.  */
  273. static int ComparePVByX(const void * Index1, const void * Index2)
  274. {
  275.     PinTypePtr    ptr1 = ((PVDataTypePtr) Index1)->Data,
  276.                 ptr2 = ((PVDataTypePtr) Index2)->Data;
  277.  
  278.     return((int) (ptr1->X -ptr2->X));
  279. }
  280.  
  281. /* ---------------------------------------------------------------------------
  282.  * returns a the maximum index which matches
  283.  * X1(line[index]) >= X for all index <= 'found one'
  284.  * the field is sorted in a descending order
  285.  */
  286. static Cardinal GetLineByLowX(Position X, Cardinal Layer)
  287. {
  288.     LineTypePtr    *ptr = LineSortedByLowX[Layer];
  289.     int            left = 0,
  290.                 right = PCB->Data->Layer[Layer].LineN -1,
  291.                 position;
  292.  
  293.     while (left < right)
  294.     {
  295.         position = (left +right) /2;
  296.         if (MIN(ptr[position]->X1, ptr[position]->X2) <= X)
  297.             right = position;
  298.         else
  299.             left = position+1;
  300.     }
  301.     return((Cardinal) left);
  302. }
  303.  
  304. /* ---------------------------------------------------------------------------
  305.  * returns a the maximum index which matches
  306.  * X2(line[index]) <= X for all index <= 'found one'
  307.  * the field is sorted in a ascending order
  308.  */
  309. static Cardinal GetLineByHighX(Position X, Cardinal Layer)
  310. {
  311.     LineTypePtr    *ptr = LineSortedByHighX[Layer];
  312.     int            left = 0,
  313.                 right = PCB->Data->Layer[Layer].LineN -1,
  314.                 position;
  315.  
  316.     while (left < right)
  317.     {
  318.         position = (left +right) /2;
  319.         if (MAX(ptr[position]->X1, ptr[position]->X2) >= X)
  320.             right = position;
  321.         else
  322.             left = position+1;
  323.     }
  324.     return((Cardinal) left);
  325. }
  326.  
  327. /* ---------------------------------------------------------------------------
  328.  * returns a the minimum index which matches
  329.  * X(PV[index]) <= X for all index <= 'found one'
  330.  * the field is sorted in a ascending order
  331.  */
  332. static Cardinal GetPVByX(Position X)
  333. {
  334.     int    left = 0,
  335.         right = TotalPV -1,
  336.         position;
  337.  
  338.     while (left < right)
  339.     {
  340.         position = (left +right) /2;
  341.         if (PVSortedByX[position].Data->X >= X)
  342.             right = position;
  343.         else
  344.             left = position+1;
  345.     }
  346.     return((Cardinal) left);
  347. }
  348.  
  349. /* ---------------------------------------------------------------------------
  350.  * releases all allocated memory
  351.  */
  352. static void FreeConnectionLookupMemory(void)
  353. {
  354.     Cardinal    i;
  355.  
  356.     for (i = 0; i < MAX_LAYER; i++)
  357.     {
  358.         MyFree((char **) &LineSortedByLowX[i]);
  359.         MyFree((char **) &LineSortedByHighX[i]);
  360.         MyFree((char **) &LineList[i].Data);
  361.         MyFree((char **) &PolygonList[i].Data);
  362.     }
  363.     MyFree((char **) &PVSortedByX);
  364.     MyFree((char **) &PVList.Data);
  365. }
  366.  
  367. /* ---------------------------------------------------------------------------
  368.  * allocates memory for stacks ...
  369.  * initializes index and sorts it by X1 and X2
  370.  */
  371. static void InitConnectionLookup(void)
  372. {
  373.     Cardinal    i,
  374.     pos;
  375.  
  376.         /* initialize line and polygon data */
  377.     for (i = 0; i < MAX_LAYER; i++)
  378.     {
  379.         LayerTypePtr    layer = &PCB->Data->Layer[i];
  380.  
  381.         if (layer->LineN)
  382.         {
  383.                 /* allocate memory for line pointer lists */
  384.             LineSortedByLowX[i] = (LineTypePtr *) MyCalloc(layer->LineN,
  385.                 sizeof(LineTypePtr), "InitConnectionLookup()");
  386.             LineSortedByHighX[i] = (LineTypePtr *) MyCalloc(layer->LineN,
  387.                 sizeof(LineTypePtr), "InitConnectionLookup()");
  388.             LineList[i].Data = (void **) MyCalloc(layer->LineN,
  389.                 sizeof(LineTypePtr), "InitConnectionLookup()");
  390.  
  391.                 /* copy addresses to arrays and sort them */
  392.             LINE_LOOP(layer,
  393.                 LineSortedByLowX[i][n] = LineSortedByHighX[i][n] = line;
  394.             );
  395.             qsort(LineSortedByLowX[i], layer->LineN, sizeof(LineTypePtr),
  396.                 CompareLineByLowX);
  397.             qsort(LineSortedByHighX[i], layer->LineN, sizeof(LineTypePtr),
  398.                 CompareLineByHighX);
  399.         }
  400.  
  401.             /* allocate memory for polygon list */
  402.         if (layer->PolygonN)
  403.             PolygonList[i].Data = (void **) MyCalloc(layer->PolygonN,
  404.                 sizeof(PolygonTypePtr), "InitConnectionLookup()");
  405.  
  406.             /* clear some struct members */
  407.         LineList[i].Position = 0;
  408.         LineList[i].DrawPosition = 0;
  409.         LineList[i].Number = 0;
  410.         PolygonList[i].Position = 0;
  411.         PolygonList[i].DrawPosition = 0;
  412.         PolygonList[i].Number = 0;
  413.     }
  414.  
  415.         /* pin and via data; start with counting their total number,
  416.          * then allocate memory and copy the data to a tmp field
  417.          * set number of the according element in tmp field too
  418.          */
  419.     TotalPV = PCB->Data->ViaN;
  420.     ELEMENT_LOOP(PCB->Data, TotalPV += element->PinN; );
  421.     PVSortedByX = (PVDataTypePtr) MyCalloc(TotalPV, sizeof(PVDataType),
  422.         "InitConnectionLookup()");
  423.  
  424.         /* copy via data; field is initialized with NULL */
  425.     pos = 0;
  426.     VIA_LOOP(PCB->Data, PVSortedByX[pos++].Data = via; );
  427.     ELEMENT_LOOP(PCB->Data,
  428.         PIN_LOOP(element,
  429.             PVSortedByX[pos].Data = pin;
  430.             PVSortedByX[pos++].Element = element;
  431.         );
  432.     );
  433.  
  434.         /* sort array by X */
  435.     qsort(PVSortedByX, TotalPV, sizeof(PVDataType), ComparePVByX);
  436.  
  437.         /* allocate memory for 'new PV to check' list and clear struct */
  438.     PVList.Data = (void **) MyCalloc(TotalPV, sizeof(PVDataTypePtr),
  439.         "InitConnectionLookup()");
  440.     PVList.Position = 0;
  441.     PVList.DrawPosition = 0;
  442.     PVList.Number = 0;
  443. }
  444.  
  445. /* ---------------------------------------------------------------------------
  446.  * returns a pointer into the sorted list with the highest index and the
  447.  * number of entries left to check
  448.  * All list entries starting from the pointer position to the end
  449.  * may match the specified x coordinate range.
  450.  */
  451. static LineTypePtr *GetIndexOfLines(Position Xlow, Position Xhigh,
  452.     Cardinal Layer, Cardinal *Number)
  453. {
  454.     Cardinal    index1,
  455.                 index2;
  456.  
  457.         /* get index of the first line that may match the coordinates
  458.          * see GetLineByLowX(), GetLineByHighX()
  459.          * take the field with less entries to speed up searching
  460.          */
  461.     index1 = GetLineByLowX(Xhigh, Layer);
  462.     index2 = GetLineByHighX(Xlow, Layer);
  463.     if (index1 > index2)
  464.     {
  465.         *Number = PCB->Data->Layer[Layer].LineN -index1;
  466.         return(&LineSortedByLowX[Layer][index1]);
  467.     }
  468.     *Number = PCB->Data->Layer[Layer].LineN -index2;
  469.     return(&LineSortedByHighX[Layer][index2]);
  470. }
  471.  
  472. /* ---------------------------------------------------------------------------
  473.  * finds a PV by it's coordinates in the sorted list
  474.  * A pointer to the list entry or NULL is returned
  475.  */
  476. static PVDataTypePtr LookupPVByCoordinates(Position X, Position Y)
  477. {
  478.     Cardinal    i, limit;
  479.  
  480.         /* get absolute lower/upper boundary */
  481.     i = GetPVByX(X -MAX_PINORVIASIZE);
  482.     limit = GetPVByX(X +MAX_PINORVIASIZE +1);
  483.     while (i <= limit)
  484.     {
  485.         PinTypePtr    ptr = PVSortedByX[i].Data;
  486.  
  487.             /* check which one matches */
  488.         if (abs(ptr->X - X) <= ptr->Thickness/4 &&
  489.             abs(ptr->Y - Y) <= ptr->Thickness/4)
  490.             return(&PVSortedByX[i]);
  491.         i++;
  492.     }
  493.     return(NULL);
  494. }
  495.  
  496. /* ---------------------------------------------------------------------------
  497.  * checks if a PV is connected to LOs, if it is, the LO is added to
  498.  * the appropriate list and the 'used' flag is set
  499.  */
  500. static void LookupLOConnectionsToPVList(void)
  501. {
  502.     PinTypePtr    pv;
  503.     Cardinal    layer;
  504.  
  505.         /* loop over all PVs currently on list */
  506.     while (PVList.Position < PVList.Number)
  507.     {
  508.             /* get pointer to data */
  509.         pv = PVLIST_ENTRY(PVList.Position)->Data;
  510.  
  511.         for (layer = 0; layer < MAX_LAYER; layer++)
  512.         {
  513.             PolygonTypePtr    polygon = PCB->Data->Layer[layer].Polygon;
  514.             Dimension        distance = (MAX_LINESIZE + pv->Thickness) /3;
  515.             LineTypePtr        *sortedptr;
  516.             Cardinal        i;
  517.  
  518.                 /* get the lowest data pointer of lines which may have
  519.                  * a connection to the PV ### line->X1 <= line->X2 ###
  520.                  */
  521.             sortedptr = GetIndexOfLines(pv->X -distance, pv->X +distance,
  522.                 layer, &i);
  523.             for (; i; i--, sortedptr++)
  524.                 if (!TEST_FLAG(FOUNDFLAG, *sortedptr) &&
  525.                     IS_PV_ON_LINE(pv, *sortedptr))
  526.                     ADD_LINE_TO_LIST(layer, *sortedptr);
  527.  
  528.                 /* check all polygons */
  529.             for (i = 0; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
  530.                 if (!TEST_FLAG(FOUNDFLAG, polygon) &&
  531.                     IsPointInPolygon(polygon, pv->X, pv->Y))
  532.                     ADD_POLYGON_TO_LIST(layer, polygon);
  533.         }
  534.         PVList.Position++;
  535.     }
  536. }
  537.  
  538. /* ---------------------------------------------------------------------------
  539.  * find all connections between LO at the current list position and new LOs
  540.  */
  541. static void LookupLOConnectionsToLOList(void)
  542. {
  543.     Cardinal    i,
  544.                 group;
  545.     Cardinal    lineposition[MAX_LAYER],
  546.                 polyposition[MAX_LAYER];
  547.  
  548.         /* copy the current LO list positions; the original data is changed
  549.          * by 'LookupPVConnectionsToLOList()' which has to check the same
  550.          * list entries plus the new ones
  551.          */
  552.     for (i = 0; i< MAX_LAYER; i++)
  553.     {
  554.         lineposition[i] = LineList[i].Position;
  555.         polyposition[i] = PolygonList[i].Position;
  556.     }
  557.     
  558.         /* loop over all layergroups */
  559.     for (group = 0; group < MAX_LAYER; group++)
  560.     {
  561.         Cardinal    entry;
  562.         Boolean        done;
  563.  
  564.             /* loop over all new LOs in the list;
  565.              * recurse till no more new connections n the layergroup were found
  566.              */
  567.         do
  568.         {
  569.             for (entry = 0; entry < PCB->LayerGroups.Number[group]; entry++)
  570.             {
  571.                 Cardinal    layer = PCB->LayerGroups.Entries[group][entry];
  572.                 Cardinal    *position;
  573.  
  574.                     /* try all new lines */
  575.                 position = &lineposition[layer];
  576.                 for (; *position < LineList[layer].Number; (*position)++)
  577.                     LookupLOConnectionsToLine(
  578.                         LINELIST_ENTRY(layer, *position), group);
  579.  
  580.                     /* try all new polygons */
  581.                 position = &polyposition[layer];
  582.                 for (; *position < PolygonList[layer].Number; (*position)++)
  583.                     LookupLOConnectionsToPolygon(
  584.                         POLYGONLIST_ENTRY(layer, *position), group);
  585.             }
  586.  
  587.                 /* check if both lists are handled, the second for-loop may
  588.                  * have changed the line list
  589.                  */
  590.             done = True;
  591.             for (entry = 0; entry < PCB->LayerGroups.Number[group]; entry++)
  592.             {
  593.                 Cardinal    layer = PCB->LayerGroups.Entries[group][entry];
  594.  
  595.                 done = done &&
  596.                     lineposition[layer] >= LineList[layer].Number &&
  597.                     polyposition[layer] >= PolygonList[layer].Number;
  598.             }
  599.         } while (!done);
  600.     }
  601. }
  602.  
  603. /* ---------------------------------------------------------------------------
  604.  * searches for new PVs that are connected to NEW LOs on the list
  605.  * This routine updates the position counter of the lists too.
  606.  */
  607. static void LookupPVConnectionsToLOList(void)
  608. {
  609.     Cardinal    layer,
  610.                 i,
  611.                 limit;
  612.     Dimension    distance;
  613.  
  614.         /* loop over all layers */
  615.     for (layer = 0; layer < MAX_LAYER; layer++)
  616.     {
  617.             /* check all lines */
  618.         while (LineList[layer].Position < LineList[layer].Number)
  619.         {
  620.             LineTypePtr    line = LINELIST_ENTRY(layer, LineList[layer].Position);
  621.  
  622.                 /* get the positions in sorted field to speed up searching
  623.                  * ### line->X1 <= line->X2 ###
  624.                  * the '+1' in the second call of GetPVByX()
  625.                  * makes sure that 'limit' is realy the position outside the
  626.                  * range
  627.                  */
  628.             distance = (MAX_PINORVIASIZE +line->Thickness) /3;
  629.             i = GetPVByX(line->X1 -distance);
  630.             limit = GetPVByX(line->X2 +distance +1);
  631.             for (; i <= limit; i++)
  632.             {
  633.                 PinTypePtr    pv = PVSortedByX[i].Data;
  634.  
  635.                 if (!TEST_FLAG(FOUNDFLAG, pv) && IS_PV_ON_LINE(pv, line))
  636.                     ADD_PV_TO_LIST(&PVSortedByX[i]);
  637.             }
  638.             LineList[layer].Position++;
  639.         }
  640.  
  641.             /* now all polygons */
  642.         while (PolygonList[layer].Position < PolygonList[layer].Number)
  643.         {
  644.             PolygonTypePtr    polygon;
  645.  
  646.             polygon = POLYGONLIST_ENTRY(layer, PolygonList[layer].Position);
  647.  
  648.                 /* get the positions in sorted field to speed up searching */
  649.             distance = MAX_PINORVIASIZE /3;
  650.             i = GetPVByX(polygon->BoundingBox.X1 -distance);
  651.             limit = GetPVByX(polygon->BoundingBox.X2 +distance +1);
  652.             for (; i <= limit; i++)
  653.             {
  654.                 PinTypePtr    pv = PVSortedByX[i].Data;
  655.                 
  656.                 if (!TEST_FLAG(FOUNDFLAG, pv) &&
  657.                     IsPointInPolygon(polygon, pv->X, pv->Y))
  658.                     ADD_PV_TO_LIST(&PVSortedByX[i]);
  659.             }
  660.             PolygonList[layer].Position++;
  661.         }
  662.     }
  663. }
  664.  
  665. /* ---------------------------------------------------------------------------
  666.  * checks if two lines intersect
  667.  * constant recognition by the optimizer is assumed
  668.  * from news FAQ:
  669.  *
  670.  *  Let A,B,C,D be 2-space position vectors.  Then the directed line
  671.  *  segments AB & CD are given by:
  672.  *
  673.  *      AB=A+r(B-A), r in [0,1]
  674.  *      CD=C+s(D-C), s in [0,1]
  675.  *
  676.  *  If AB & CD intersect, then
  677.  *
  678.  *      A+r(B-A)=C+s(D-C), or
  679.  *
  680.  *      XA+r(XB-XA)=XC+s(XD-XC)
  681.  *      YA+r(YB-YA)=YC+s(YD-YC)  for some r,s in [0,1]
  682.  *
  683.  *  Solving the above for r and s yields
  684.  *
  685.  *          (YA-YC)(XD-XC)-(XA-XC)(YD-YC)
  686.  *      r = -----------------------------  (eqn 1)
  687.  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
  688.  *
  689.  *          (YA-YC)(XB-XA)-(XA-XC)(YB-YA)
  690.  *      s = -----------------------------  (eqn 2)
  691.  *          (XB-XA)(YD-YC)-(YB-YA)(XD-XC)
  692.  *
  693.  *  Let I be the position vector of the intersection point, then
  694.  *
  695.  *      I=A+r(B-A) or
  696.  *
  697.  *      XI=XA+r(XB-XA)
  698.  *      YI=YA+r(YB-YA)
  699.  *
  700.  *  By examining the values of r & s, you can also determine some
  701.  *  other limiting conditions:
  702.  *
  703.  *      If 0<=r<=1 & 0<=s<=1, intersection exists
  704.  *          r<0 or r>1 or s<0 or s>1 line segments do not intersect
  705.  *
  706.  *      If the denominator in eqn 1 is zero, AB & CD are parallel
  707.  *      If the numerator in eqn 1 is also zero, AB & CD are coincident
  708.  *
  709.  *  If the intersection point of the 2 lines are needed (lines in this
  710.  *  context mean infinite lines) regardless whether the two line
  711.  *  segments intersect, then
  712.  *
  713.  *      If r>1, I is located on extension of AB
  714.  *      If r<0, I is located on extension of BA
  715.  *      If s>1, I is located on extension of CD
  716.  *      If s<0, I is located on extension of DC
  717.  *
  718.  *  Also note that the denominators of eqn 1 & 2 are identical.
  719.  *
  720.  *
  721.  *
  722.  *
  723.  *
  724.  */
  725. static Boolean LineLineIntersect(LineTypePtr Line1, LineTypePtr Line2)
  726. {
  727.     float    r, s,
  728.             denum,
  729.             radius,
  730.             dx, dy;
  731.  
  732.     denum = (float) (Line1->X2 -Line1->X1)*(float) (Line2->Y2 -Line2->Y1) -
  733.         (float) (Line1->Y2 -Line1->Y1)*(float) (Line2->X2 -Line2->X1);
  734.  
  735.         /* handle parallel lines */
  736.     if (denum == 0.0)
  737.     {
  738.             /* at least one of the two end points of one segment
  739.              * has to have a minimum distance to the other segment
  740.              */
  741.         return(
  742.             IsPointOnLine(Line1->X1, Line1->Y1, Line1->Thickness/2.0, Line2) ||
  743.             IsPointOnLine(Line1->X2, Line1->Y2, Line1->Thickness/2.0, Line2) ||
  744.             IsPointOnLine(Line2->X1, Line2->Y1, Line2->Thickness/2.0, Line1) ||
  745.             IsPointOnLine(Line2->X2, Line2->Y2, Line2->Thickness/2.0, Line1));
  746.     }
  747.  
  748.     r = (float) (Line1->Y1 -Line2->Y1)*(float) (Line2->X2 -Line2->X1) -
  749.         (float) (Line1->X1 -Line2->X1)*(float) (Line2->Y2 -Line2->Y1);
  750.     r /= denum;
  751.     s = (float) (Line1->Y1 -Line2->Y1)*(float) (Line1->X2 -Line1->X1) -
  752.         (float) (Line1->X1 -Line2->X1)*(float) (Line1->Y2 -Line1->Y1);
  753.     s /= denum;
  754.  
  755.         /* intersection is at least on AB */
  756.     if (r >= 0.0 && r <= 1.0)
  757.     {
  758.         if (s >= 0.0 && s <= 1.0)
  759.             return(True);
  760.  
  761.             /* intersection on AB and extension of CD */
  762.         return(s < 0.0 ?
  763.             IsPointOnLine(Line2->X1, Line2->Y1, Line2->Thickness/2.0, Line1) :
  764.             IsPointOnLine(Line2->X2, Line2->Y2, Line2->Thickness/2.0, Line1));
  765.     }
  766.  
  767.         /* intersection is on least on CD */
  768.     if (s >= 0.0 && s <= 1.0)
  769.     {
  770.             /* intersection on CD and extension of AB */
  771.         return(r < 0.0 ?
  772.             IsPointOnLine(Line1->X1, Line1->Y1, Line1->Thickness/2.0, Line2) :
  773.             IsPointOnLine(Line1->X2, Line1->Y2, Line1->Thickness/2.0, Line2));
  774.     }
  775.  
  776.         /* no intersection of zero-width lines but maybe of thick lines;
  777.          * we just have two check the distance of the endpoint of the two
  778.          * segments which are next to the intersection point
  779.          */
  780.     radius = (float) (Line1->Thickness +Line2->Thickness)/2.0 +1.0;
  781.     radius *= radius;
  782.     if (s < 0.0)
  783.     {
  784.         dx = (float) ((r < 0.0 ? Line1->X1 : Line1->X2) -Line2->X1);
  785.         dy = (float) ((r < 0.0 ? Line1->Y1 : Line1->Y2) -Line2->Y1);
  786.  
  787.         return(dx*dx +dy*dy <= radius);
  788.     }
  789.     dx = (float) ((r < 0.0 ? Line1->X1 : Line1->X2) -Line2->X2);
  790.     dy = (float) ((r < 0.0 ? Line1->Y1 : Line1->Y2) -Line2->Y2);
  791.     return(dx*dx +dy*dy <= radius);
  792. }
  793.  
  794. /* ---------------------------------------------------------------------------
  795.  * searches all LOs that are connected to the given line on the given
  796.  * layergroup. All found connections are added to the list
  797.  *
  798.  * the notation that is used is:
  799.  * Xij means Xj at line i
  800.  */
  801. static void LookupLOConnectionsToLine(LineTypePtr Line, Cardinal LayerGroup)
  802. {
  803.     Cardinal    entry;
  804.     Dimension    distance;
  805.  
  806.         /* the maximum possible distance */
  807.     distance = (Line->Thickness +MAX_LINESIZE) /2;
  808.  
  809.         /* loop over all layers of the group */
  810.     for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
  811.     {
  812.         PolygonTypePtr    polygon;
  813.         LineTypePtr        *sortedptr;
  814.         Cardinal        layer,
  815.                         i;
  816.  
  817.             /* get index of the first line that may match the coordinates */
  818.         layer = PCB->LayerGroups.Entries[LayerGroup][entry];
  819.         sortedptr = GetIndexOfLines(Line->X1 -distance, Line->X2 +distance,
  820.             layer, &i);
  821.  
  822.             /* loop till the end of the data is reached
  823.              * DONT RETRY LINES THAT HAVE BEEN FOUND
  824.              */
  825.         for (; i; i--, sortedptr++)
  826.             if (!TEST_FLAG(FOUNDFLAG, *sortedptr) &&
  827.                 LineLineIntersect(Line, *sortedptr))
  828.                 ADD_LINE_TO_LIST(layer, *sortedptr);
  829.  
  830.             /* now check all polygons */
  831.         i = 0;
  832.         polygon = PCB->Data->Layer[layer].Polygon;
  833.         for (; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
  834.             if (!TEST_FLAG(FOUNDFLAG, polygon) &&
  835.                 IsLineInPolygon(Line, polygon))
  836.                 ADD_POLYGON_TO_LIST(layer, polygon);
  837.     }
  838. }
  839.  
  840. /* ---------------------------------------------------------------------------
  841.  * looks up LOs that are connected to the given polygon
  842.  * on the given layergroup. All found connections are added to the list
  843.  */
  844. static void LookupLOConnectionsToPolygon(PolygonTypePtr Polygon,
  845.     Cardinal LayerGroup)
  846. {
  847.     Cardinal    entry;
  848.  
  849.         /* loop over all layers of the group */
  850.     for (entry = 0; entry < PCB->LayerGroups.Number[LayerGroup]; entry++)
  851.     {
  852.         PolygonTypePtr    polygon;
  853.         LineTypePtr        *sortedptr;
  854.         Cardinal        layer,
  855.                         i;
  856.  
  857.         layer = PCB->LayerGroups.Entries[LayerGroup][entry];
  858.  
  859.             /* check all polygons */
  860.         polygon = PCB->Data->Layer[layer].Polygon;
  861.         for (i = 0; i < PCB->Data->Layer[layer].PolygonN; i++, polygon++)
  862.             if (!TEST_FLAG(FOUNDFLAG, polygon) &&
  863.                 IsPolygonInPolygon(polygon, Polygon))
  864.                 ADD_POLYGON_TO_LIST(layer, polygon);
  865.  
  866.             /* and now check all lines, first reduce the number of lines by
  867.              * evaluating the coordinates from the sorted lists
  868.              */
  869.         sortedptr = GetIndexOfLines(Polygon->BoundingBox.X1 -MAX_LINESIZE/2,
  870.             Polygon->BoundingBox.X2 +MAX_LINESIZE/2, layer, &i);
  871.  
  872.             /* now check all lines that match the condition */
  873.         for (; i; i--, sortedptr++)
  874.             if (!TEST_FLAG(FOUNDFLAG, *sortedptr) &&
  875.                 IsLineInPolygon(*sortedptr, Polygon))
  876.                 ADD_LINE_TO_LIST(layer, *sortedptr);
  877.     }
  878. }
  879.  
  880. /* ---------------------------------------------------------------------------
  881.  * checks if a line has a connection to a polygon
  882.  *
  883.  * - first check if the line can intersect with the polygon by
  884.  *   evaluating the bounding boxes
  885.  * - check the two end points of the line. If none of them matches
  886.  * - check all segments of the polygon agains the line.
  887.  */
  888. static Boolean IsLineInPolygon(LineTypePtr Line, PolygonTypePtr Polygon)
  889. {
  890.     if (MIN(Line->X1, Line->X2) <= Polygon->BoundingBox.X2 &&
  891.         MIN(Line->Y1, Line->Y2) <= Polygon->BoundingBox.Y2 &&
  892.         MAX(Line->X1, Line->X2) >= Polygon->BoundingBox.X1 &&
  893.         MAX(Line->Y1, Line->Y2) >= Polygon->BoundingBox.Y1)
  894.     {
  895.         LineType    line;
  896.  
  897.         if (IsPointInPolygon(Polygon, Line->X1, Line->Y1) ||
  898.             IsPointInPolygon(Polygon, Line->X2, Line->Y2))
  899.             return(True);
  900.  
  901.             /* check all lines, start with the connection of the first-last
  902.              * polygon point; POLYGONPOINT_LOOP decrements the pointers !!!
  903.              */
  904.         line.X1 = Polygon->Points[0].X;
  905.         line.Y1 = Polygon->Points[0].Y;
  906.         line.Thickness = 0;
  907.         POLYGONPOINT_LOOP(Polygon,
  908.             line.X2 = point->X;
  909.             line.Y2 = point->Y;
  910.             if (LineLineIntersect(Line, &line))
  911.                 return(True);
  912.             line.X1 = line.X2;
  913.             line.Y1 = line.Y2;
  914.         );
  915.     }
  916.     return(False);
  917. }
  918.  
  919. /* ---------------------------------------------------------------------------
  920.  * checks if a polygon has a connection to a second one
  921.  *
  922.  * First check all points out of P1 against P2 and vice versa.
  923.  * If both fail check all lines of P1 agains the ones of P2
  924.  */
  925. static Boolean IsPolygonInPolygon(PolygonTypePtr P1, PolygonTypePtr P2)
  926. {
  927.         /* first check if both bounding boxes intersect */
  928.     if (P1->BoundingBox.X1 <= P2->BoundingBox.X2 &&
  929.         P1->BoundingBox.X2 >= P2->BoundingBox.X1 &&
  930.         P1->BoundingBox.Y1 <= P2->BoundingBox.Y2 &&
  931.         P1->BoundingBox.Y2 >= P2->BoundingBox.Y1)
  932.     {
  933.         LineType    line;
  934.  
  935.         POLYGONPOINT_LOOP(P1,
  936.             if (IsPointInPolygon(P2, point->X, point->Y))
  937.                 return(True);
  938.         );
  939.         POLYGONPOINT_LOOP(P2,
  940.             if (IsPointInPolygon(P1, point->X, point->Y))
  941.                 return(True);
  942.         );
  943.  
  944.             /* check all lines of P1 agains P2;
  945.              * POLYGONPOINT_LOOP decrements the pointer !!!
  946.              */
  947.         line.X1 = P1->Points[0].X;
  948.         line.Y1 = P1->Points[1].Y;
  949.         line.Thickness = 0;
  950.         POLYGONPOINT_LOOP(P1,
  951.             line.X2 = point->X;
  952.             line.Y2 = point->Y;
  953.             if (IsLineInPolygon(&line, P2))
  954.                 return(True);
  955.             line.X1 = line.X2;
  956.             line.Y1 = line.Y2;
  957.         );
  958.     }
  959.     return(False);
  960. }
  961.  
  962. /* ---------------------------------------------------------------------------
  963.  * prints all found connections of a pin to file FP
  964.  * the connections are stacked in 'PVList'
  965.  */
  966. static void PrintPinConnections(FILE *FP)
  967. {
  968.     Cardinal        i,
  969.                     indent,
  970.                     linelength;
  971.     PVDataTypePtr    pv;
  972.     char            *ename,
  973.                     *pname;
  974.     size_t            len;
  975.  
  976.         /* the staring pin */
  977.     pv = PVLIST_ENTRY(0);
  978.     pname = UNKNOWN(pv->Data->Name);
  979.     fprintf(FP, "  %s: ", pname);
  980.     linelength = indent = strlen(pname) +4;
  981.  
  982.         /* start with 'i' == 1 because entry[0] is the starting pin itself */
  983.     for (i = 1; i < PVList.Number; i++)
  984.     {
  985.         pv = PVLIST_ENTRY(i);
  986.         pname = EMPTY(pv->Data->Name);
  987.  
  988.             /* get the elements name or assume that its a via */
  989.         ename = pv->Element ? UNKNOWN(ELEMENT_NAME(PCB, pv->Element)) : "via"; 
  990.  
  991.             /* new line ? */
  992.         len = 4 +strlen(pname) +strlen(ename);
  993.         linelength += len;
  994.         if (linelength >= Settings.CharPerLine)
  995.         {
  996.             linelength = indent +len;
  997.             fprintf(FP, "\n%*s%s(%s), ", (int) indent, "", pname, ename);
  998.         }
  999.         else
  1000.             fprintf(FP, "%s(%s), ", pname, ename);
  1001.     }
  1002.  
  1003.         /* there might be only one pin in list --> no connections */
  1004.     if (PVList.Number == 1)
  1005.         fputs("no connection", FP);
  1006.     fputc('\n', FP);
  1007. }
  1008.  
  1009. /* ---------------------------------------------------------------------------
  1010.  * checks if all lists of new objects are handled
  1011.  */
  1012. static Boolean ListsEmpty(void)
  1013. {
  1014.     Boolean    empty;
  1015.     int        i;
  1016.  
  1017.     empty = (PVList.Position >= PVList.Number);
  1018.     for (i = 0; i < MAX_LAYER && empty; i++)
  1019.         empty = empty &&
  1020.             LineList[i].Position >= LineList[i].Number &&
  1021.             PolygonList[i].Position >= PolygonList[i].Number;
  1022.     return(empty);
  1023. }
  1024.  
  1025. /* ---------------------------------------------------------------------------
  1026.  * loops till no more connections are found 
  1027.  */
  1028. static void DoIt(void)
  1029. {
  1030.     do
  1031.     {
  1032.             /* lookup connections; these are the steps (2) to (4)
  1033.              * from the description
  1034.              */
  1035.         LookupLOConnectionsToPVList();
  1036.         LookupLOConnectionsToLOList();
  1037.         LookupPVConnectionsToLOList();
  1038.         DrawNewConnections();
  1039.     } while (!ListsEmpty());
  1040. }
  1041.  
  1042. /* ---------------------------------------------------------------------------
  1043.  * prints all unused pins of an element to file FP
  1044.  */
  1045. static Boolean PrintAndSelectUnusedPinsOfElement(ElementTypePtr Element,
  1046.     FILE *FP)
  1047. {
  1048.     size_t        indent = 0,            /* init to get rid of compiler warning */
  1049.                 linelength = 0;
  1050.     Boolean        first = True;
  1051.  
  1052.         /* check all pins in element */
  1053.     PIN_LOOP(Element,
  1054.         {
  1055.             PVDataTypePtr    entry;
  1056.  
  1057.                 /* lookup pin in list */
  1058.             entry = LookupPVByCoordinates(pin->X, pin->Y);
  1059.  
  1060.                 /* pin might has bee checked before, add to list if not */
  1061.             if (!TEST_FLAG(FOUNDFLAG, entry->Data) && FP)
  1062.             {
  1063.                 Cardinal    layer;
  1064.  
  1065.                 ADD_PV_TO_LIST(entry);
  1066.                 DoIt();
  1067.  
  1068.                     /* the pin has no connection if it's the
  1069.                      * only list entry
  1070.                      */
  1071.                 if (PVList.Number == 1)
  1072.                 {
  1073.                     char    *pname = EMPTY(entry->Data->Name);
  1074.                     size_t    len = strlen(pname) +2;
  1075.  
  1076.                         /* output of element name if not already done */
  1077.                     if (first)
  1078.                     {
  1079.                         fprintf(FP, "%s(%s): ",UNKNOWN(CANONICAL_NAME(Element)),
  1080.                             UNKNOWN(NAMEONPCB_NAME(Element)));
  1081.                         indent = strlen(UNKNOWN(CANONICAL_NAME(Element))) +
  1082.                             strlen(UNKNOWN(NAMEONPCB_NAME(Element))) +4;
  1083.                         linelength = indent;
  1084.                         first = False;
  1085.                     }
  1086.  
  1087.                         /* new line ? */
  1088.                     linelength += len;
  1089.                     if (linelength >= Settings.CharPerLine)
  1090.                     {
  1091.                         linelength = indent +len;
  1092.                         fprintf(FP, "\n%*s%s, ", (int) indent, "", pname);
  1093.                     }
  1094.                     else
  1095.                         fprintf(FP, "%s, ", pname);
  1096.  
  1097.                         /* select object */
  1098.                     SET_FLAG(SELECTEDFLAG, entry->Data);
  1099.                     DrawPin(entry->Data);
  1100.                 }
  1101.  
  1102.                     /* reset found LOs for the next pin */
  1103.                 for (layer = 0; layer < MAX_LAYER; layer++)
  1104.                 {
  1105.                     LineList[layer].Position = LineList[layer].Number = 0;
  1106.                     PolygonList[layer].Position = PolygonList[layer].Number = 0;
  1107.                 }
  1108.                 PVList.Number = PVList.Position = 0;
  1109.                 if (CheckAbort())
  1110.                 {
  1111.                     fputs("\n\nABORTED...\n", FP);
  1112.                     return(True);
  1113.                 }
  1114.             }
  1115.         }
  1116.     );
  1117.         
  1118.         /* print seperator if element has unused pins */
  1119.     if (!first)
  1120.     {
  1121.         fputc('\n', FP);
  1122.         SEPERATE(FP);
  1123.     }
  1124.     return(False);
  1125. }
  1126.  
  1127. /* ---------------------------------------------------------------------------
  1128.  * finds all connections to the pins of the passed element.
  1129.  * The result is written to filedescriptor 'FP'
  1130.  * Returns True if operation was aborted
  1131.  */
  1132. static Boolean PrintElementConnections(ElementTypePtr Element,
  1133.     FILE *FP)
  1134. {
  1135.     Cardinal    layer;
  1136.  
  1137.     fprintf(FP, "%s(%s)\n", UNKNOWN(CANONICAL_NAME(Element)),
  1138.         UNKNOWN(NAMEONPCB_NAME(Element)));
  1139.  
  1140.         /* check all pins in element */
  1141.     PIN_LOOP(Element,
  1142.         {
  1143.             PVDataTypePtr    entry;
  1144.  
  1145.                 /* lookup pin in list */
  1146.             entry = LookupPVByCoordinates(pin->X, pin->Y);
  1147.  
  1148.                 /* pin might has bee checked before, add to list if not */
  1149.             if (TEST_FLAG(FOUNDFLAG, entry->Data) && FP)
  1150.             {
  1151.                 fprintf(FP, "  %s: has been checked before\n",
  1152.                     UNKNOWN(pin->Name));
  1153.                 continue;
  1154.             }
  1155.             ADD_PV_TO_LIST(entry);
  1156.             DoIt();
  1157.  
  1158.                 /* printout all found connections */
  1159.             PrintPinConnections(FP);
  1160.  
  1161.                 /* reset found LOs for the next pin */
  1162.             for (layer = 0; layer < MAX_LAYER; layer++)
  1163.             {
  1164.                 LineList[layer].Position = LineList[layer].Number = 0;
  1165.                 PolygonList[layer].Position = PolygonList[layer].Number = 0;
  1166.             }
  1167.             PVList.Number = PVList.Position = 0;
  1168.             if (CheckAbort())
  1169.             {
  1170.                 fputs("\n\nABORTED...\n", FP);
  1171.                 return(True);
  1172.             }
  1173.         }
  1174.     );
  1175.     return(False);
  1176. }
  1177.  
  1178. /* ---------------------------------------------------------------------------
  1179.  * draws all new connections which have been found since the
  1180.  * routine was called the last time
  1181.  */
  1182. static void DrawNewConnections(void)
  1183. {
  1184.     int        i;
  1185.  
  1186.         /* decrement 'i' to keep layerstack order */
  1187.     for (i = MAX_LAYER-1; i != -1; i--)
  1188.     {
  1189.         Cardinal    layer = LayerStack[i],
  1190.                     position;
  1191.  
  1192.         if (PCB->Data->Layer[layer].On)
  1193.         {
  1194.                 /* draw all new lines */
  1195.             position = LineList[layer].DrawPosition;
  1196.             for (; position < LineList[layer].Number; position++)
  1197.                 DrawLine(&PCB->Data->Layer[layer],
  1198.                     LINELIST_ENTRY(layer, position));
  1199.             LineList[layer].DrawPosition = LineList[layer].Number;
  1200.             
  1201.                 /* draw all new polygons */
  1202.             position = PolygonList[layer].DrawPosition;
  1203.             for (; position < PolygonList[layer].Number; position++)
  1204.                 DrawPolygon(&PCB->Data->Layer[layer],
  1205.                     POLYGONLIST_ENTRY(layer, position));
  1206.             PolygonList[layer].DrawPosition = PolygonList[layer].Number;
  1207.         }
  1208.     }
  1209.  
  1210.         /* draw all new PVs; 'PVList' holds an array of pointers to the
  1211.          * array of sorted pointers to PV data
  1212.          */
  1213.     while (PVList.DrawPosition < PVList.Number)
  1214.     {
  1215.         PVDataTypePtr    pv = PVLIST_ENTRY(PVList.DrawPosition);
  1216.  
  1217.         if (TEST_FLAG(PINFLAG, pv->Data))
  1218.         {
  1219.             if (PCB->PinOn)
  1220.                 DrawPin(pv->Data);
  1221.         }
  1222.         else
  1223.             if (PCB->ViaOn)
  1224.                 DrawVia(pv->Data);
  1225.         PVList.DrawPosition++;
  1226.     }
  1227. }
  1228.  
  1229. /* ---------------------------------------------------------------------------
  1230.  * find all connections to pins within one element
  1231.  */
  1232. void LookupElementConnections(ElementTypePtr Element, FILE *FP)
  1233. {
  1234.         /* reset all currently marked connections */
  1235.     CreateAbortDialog();
  1236.     ResetConnections();
  1237.     InitConnectionLookup();
  1238.     PrintElementConnections(Element, FP);
  1239.     SetChangedFlag(True);
  1240.     EndDialog(Popup);
  1241.     if (Settings.RingBellWhenFinished)
  1242.         XBell(Dpy, Settings.Volume);
  1243.     FreeConnectionLookupMemory();
  1244.     RedrawOutput();
  1245. }
  1246.  
  1247. /* ---------------------------------------------------------------------------
  1248.  * find all connections to pins of all element
  1249.  */
  1250. void LookupConnectionsToAllElements(FILE *FP)
  1251. {
  1252.         /* reset all currently marked connections */
  1253.     CreateAbortDialog();
  1254.     ResetConnections();
  1255.     InitConnectionLookup();
  1256.  
  1257.     ELEMENT_LOOP(PCB->Data,
  1258.             /* break if abort dialog returned True */
  1259.         if (PrintElementConnections(element, FP))
  1260.             break;
  1261.         SEPERATE(FP);
  1262.         if (Settings.ResetAfterElement && n != 1)
  1263.             ResetConnections();
  1264.     );
  1265.     EndDialog(Popup);
  1266.     if (Settings.RingBellWhenFinished)
  1267.         XBell(Dpy, Settings.Volume);
  1268.     FreeConnectionLookupMemory();
  1269.     RedrawOutput();
  1270. }
  1271.  
  1272. /* ---------------------------------------------------------------------------
  1273.  * looks up all connections from the object at the given coordinates
  1274.  * the 'FOUNDFLAG' is set for all objects found
  1275.  */
  1276. void LookupConnection(Position X, Position Y)
  1277. {
  1278.     void    *ptr1, *ptr2;
  1279.     int        type;
  1280.  
  1281.         /* check if there are any pins or vias at that position */
  1282.     type = SearchObjectByPosition(LOOKUP_TYPES, &ptr1, &ptr2, X, Y);
  1283.     if (type == NO_TYPE)
  1284.         return;
  1285.  
  1286.     InitConnectionLookup();
  1287.  
  1288.         /* now add the object to the appropriate list and start scanning
  1289.          * This is step (1) from the description
  1290.          */
  1291.  
  1292.     switch(type)
  1293.     {
  1294.         case PIN_TYPE:
  1295.         case VIA_TYPE:
  1296.         {
  1297.             PVDataTypePtr    entry;
  1298.  
  1299.             entry = LookupPVByCoordinates(X, Y);
  1300.             ADD_PV_TO_LIST(entry);
  1301.             break;
  1302.         }
  1303.  
  1304.         case LINE_TYPE:
  1305.         {
  1306.             int        layer = GetLayerNumber(PCB->Data, (LayerTypePtr) ptr1);
  1307.  
  1308.             ADD_LINE_TO_LIST(layer, (LineTypePtr) ptr2);
  1309.             break;
  1310.         }
  1311.  
  1312.         case POLYGON_TYPE:
  1313.         {
  1314.             int        layer = GetLayerNumber(PCB->Data, (LayerTypePtr) ptr1);
  1315.  
  1316.             ADD_POLYGON_TO_LIST(layer, (PolygonTypePtr) ptr2);
  1317.             break;
  1318.         }
  1319.  
  1320.         default:
  1321.             return;
  1322.     }
  1323.     DoIt();
  1324.  
  1325.         /* we are done */
  1326.     if (Settings.RingBellWhenFinished)
  1327.         XBell(Dpy, Settings.Volume);
  1328.     FreeConnectionLookupMemory();
  1329. }
  1330.  
  1331. /* ---------------------------------------------------------------------------
  1332.  * find all unused pins of all element
  1333.  */
  1334. void LookupUnusedPins(FILE *FP)
  1335. {
  1336.         /* reset all currently marked connections */
  1337.     CreateAbortDialog();
  1338.     ResetConnections();
  1339.     InitConnectionLookup();
  1340.  
  1341.     ELEMENT_LOOP(PCB->Data,
  1342.             /* break if abort dialog returned True;
  1343.              * passing NULL as filedescriptor discards the normal output
  1344.              */
  1345.         if (PrintAndSelectUnusedPinsOfElement(element, FP))
  1346.             break;
  1347.     );
  1348.     EndDialog(Popup);
  1349.  
  1350.     ResetConnections();
  1351.     if (Settings.RingBellWhenFinished)
  1352.         XBell(Dpy, Settings.Volume);
  1353.     FreeConnectionLookupMemory();
  1354.     RedrawOutput();
  1355. }
  1356.  
  1357. /* ---------------------------------------------------------------------------
  1358.  * resets all used flags of pins and vias
  1359.  */
  1360. void ResetFoundPinsAndVias(void)
  1361. {
  1362.     VIA_LOOP(PCB->Data, CLEAR_FLAG(FOUNDFLAG, via); );
  1363.     ELEMENT_LOOP(PCB->Data,
  1364.         PIN_LOOP(element, CLEAR_FLAG(FOUNDFLAG, pin); );
  1365.     );
  1366.     SetChangedFlag(True);
  1367. }
  1368.  
  1369. /* ---------------------------------------------------------------------------
  1370.  * resets all used flags of LOs
  1371.  */
  1372. void ResetFoundLinesAndPolygons(void)
  1373. {
  1374.     ALLLINE_LOOP(PCB->Data, CLEAR_FLAG(FOUNDFLAG, line); );
  1375.     ALLPOLYGON_LOOP(PCB->Data, CLEAR_FLAG(FOUNDFLAG, polygon); );
  1376.     SetChangedFlag(True);
  1377. }
  1378.  
  1379. /* ---------------------------------------------------------------------------
  1380.  * resets all found connections
  1381.  */
  1382. static void ResetConnections(void)
  1383. {
  1384.     ResetFoundPinsAndVias();
  1385.     ResetFoundLinesAndPolygons();
  1386.     RedrawOutput();
  1387. }
  1388.